    //
// Created by francklinson on 2021/5/20.
//

/*
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。
 如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

例如，

[2,3,4]的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/
#include <iostream>
#include <queue>

using namespace std;

class MedianFinder {
public:
    /** initialize your data structure here. */
    priority_queue<int, vector<int>, less<>> L_maxHeap; // 左边大堆顶
    priority_queue<int, vector<int>, greater<>> R_minHeap; // 右边小堆顶
    // 左半的最大和右半的最小 求中位数

    MedianFinder() {
    }

    void addNum(int num) {
        if (L_maxHeap.size() == R_minHeap.size()) {
            R_minHeap.push(num);
//            int mid = R_minHeap.top();
            L_maxHeap.push( R_minHeap.top()); // 默认左边多
            R_minHeap.pop();
        } else {
            L_maxHeap.push(num);
//            int tmp = L_maxHeap.top();
            R_minHeap.push(L_maxHeap.top());
            L_maxHeap.pop();
        }
    }

    double findMedian() {
        return L_maxHeap.size() == R_minHeap.size() ? (double) (L_maxHeap.top() + R_minHeap.top()) / 2
                                                    : (double) L_maxHeap.top();
        //默认左侧可以多1个数字，或者多0个
    }
};


/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */

int main() {
    auto obj = new MedianFinder();
    obj->addNum(1);
    obj->addNum(2);
    cout << obj->findMedian() << endl;
    obj->addNum(3);
    cout << obj->findMedian() << endl;
    delete obj;
}
